"use strict";
/*
 * Copyright (c) 2022 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
const SPLAY_8000 = 8000;
const SPLAY_80 = 80;
const SPLAY_5 = 5;
const SPLAY_1000 = 1000;
const SPLAY_2 = 2;
const SPLAY_3 = 3;
const SPLAY_4 = 4;
const SPLAY_6 = 6;
const SPLAY_7 = 7;
const SPLAY_8 = 8;
const SPLAY_9 = 9;
const SPLAY_120 = 20;
const SPLAY_50 = 50;
const SPLAY_20 = 20;
const SPLAY_19 = 19;
class Performance {
    static now() {
        return Date.now();
    }
}
class PayloadTree0 {
    constructor(array, str) {
        this.array = array;
        this.str = str;
    }
}
class PayloadTreeDepth {
    constructor(left, right) {
        this.left = left;
        this.right = right;
    }
}
class Splay {
    constructor() {
        // Configuration.
        this.splayTree = new SplayTree();
        this.splaySampleTimeStart = 0.0;
        this.splaySamples = [];
    }
    generatePayloadTree(depth, tag) {
        if (depth === 0) {
            return new PayloadTree0([0, 1, SPLAY_2, SPLAY_3, SPLAY_4, SPLAY_5, SPLAY_6, SPLAY_7, SPLAY_8, SPLAY_9], 'String for key ' + tag + ' in leaf node');
        }
        else {
            return new PayloadTreeDepth(this.generatePayloadTree(depth - 1, tag), this.generatePayloadTree(depth - 1, tag));
        }
    }
    generateKey() {
        // The benchmark framework guarantees that Math.random is
        // deterministic; see base.js.
        return Math.random();
    }
    splayUpdateStats(time) {
        const pause = time - this.splaySampleTimeStart;
        this.splaySampleTimeStart = time;
        this.splaySamples.push(pause);
    }
    insertNewNode() {
        // Insert new node with a unique key.
        let key;
        do {
            key = this.generateKey();
        } while ((this.splayTree && this.splayTree.find(key)) !== null);
        const payload = this.generatePayloadTree(SPLAY_5, String(key));
        this.splayTree.insert(key, payload);
        return key;
    }
    /*
     * @Setup
     */
    splaySetup() {
        // Check if the platform has the performance.now high resolution timer.
        // If not, throw exception and quit.
        if (!Performance.now) {
            //deBugLog("PerformanceNowUnsupported")
            return;
        }
        this.splayTree = new SplayTree();
        this.splaySampleTimeStart = Performance.now();
        for (let i = 0; i < SPLAY_8000; i++) {
            this.insertNewNode();
            if ((i + 1) % SPLAY_20 === SPLAY_19) {
                this.splayUpdateStats(Performance.now());
            }
        }
    }
    /*
     * @Teardown
     */
    splayTearDown() {
        // Allow the garbage collector to reclaim the memory
        // used by the splay tree no matter how we exit the
        // tear down function.
        const keys = this.splayTree.exportKeys();
        this.splayTree = null;
        this.splaySamples = [];
        // Verify that the splay tree has the right size.
        const length = keys.length;
        if (length !== SPLAY_8000) {
            return;
        }
        // Verify that the splay tree has sorted, unique keys.
        for (let i = 0; i < length - 1; i++) {
            if (keys[i] >= keys[i + 1]) {
                return;
            }
        }
    }
    /*
     * @Benchmark
     */
    splayRun() {
        // Replace a few nodes in the splay tree.
        for (let i = 0; i < SPLAY_80; i++) {
            const key = this.insertNewNode();
            const greatest = this.splayTree.findGreatestLessThan(key);
            if (greatest === null) {
                this.splayTree.remove(key);
            }
            else {
                this.splayTree.remove(greatest.key);
            }
        }
        this.splayUpdateStats(Performance.now());
    }
}
/**
 ** Constructs a Splay tree.  A splay tree is a self-balancing binary
 ** search tree with the additional property that recently accessed
 ** elements are quick to access again. It performs basic operations
 ** such as insertion, look-up and removal in O(log(n)) amortized time.
 **
 ** @constructor
 **/
class SplayTree {
    constructor() {
        /**
         * Pointer to the root node of the tree.
         *
         * @type {SplayTree.Node}
         * @private
         */
        this.root = null;
    }
    /**
     * @return {boolean} Whether the tree is empty.
     */
    isEmpty() {
        return !this.root;
    }
    /**
     ** Inserts a node into the tree with the specified key and value if
     ** the tree does not already contain a node with the specified key. If
     ** the value is inserted, it becomes the root of the tree.
     *
     ** @param {number} key Key to insert into the tree.
     ** @param {*} value Value to insert into the tree.
     **/
    insert(key, value) {
        var _a;
        if (this.isEmpty()) {
            this.root = new Node(key, value);
            return;
        }
        // Splay on the key to move the last node on the search path for
        // the key to the root of the tree.
        this.splay(key);
        if (((_a = this.root) === null || _a === void 0 ? void 0 : _a.key) === key) {
            return;
        }
        let node = new Node(key, value);
        if (key > Number(this.root.key)) {
            node.left = this.root;
            node.right = this.root.right;
            this.root.right = null;
        }
        else {
            node.right = this.root;
            node.left = this.root.left;
            this.root.left = null;
        }
        this.root = node;
    }
    /**
     ** Removes a node with the specified key from the tree if the tree
     ** contains a node with this key. The removed node is returned. If the
     ** key is not found, an exception is thrown.
     *
     ** @param {number} key Key to find and remove from the tree.
     ** @return {SplayTree.Node} The removed node.
     **/
    remove(key) {
        if (this.isEmpty()) {
            return null;
        }
        this.splay(key);
        if (this.root.key !== key) {
            return null;
        }
        const removed = this.root;
        if (!this.root.left) {
            this.root = this.root.right;
        }
        else {
            const right = this.root.right;
            this.root = this.root.left;
            // Splay to make sure that the new root has an empty right child.
            this.splay(key);
            // Insert the original right child as the right child of the new root.
            this.root.right = right;
        }
        return removed;
    }
    /**
     * Returns the node having the specified key or null if the tree doesn't contain
     * a node with the specified key.
     *
     * @param {number} key Key to find in the tree.
     * @return {SplayTree.Node} Node having the specified key.
     */
    find(key) {
        var _a;
        if (this.isEmpty()) {
            return null;
        }
        this.splay(key);
        return ((_a = this.root) === null || _a === void 0 ? void 0 : _a.key) === key ? this.root : null;
    }
    /**
     * @return {SplayTree.Node} Node having the maximum key value.
     */
    findMax(optStartNode = null) {
        if (this.isEmpty()) {
            return null;
        }
        let current = optStartNode || this.root;
        while (current.right) {
            current = current.right;
        }
        return current;
    }
    /**
     * @return {SplayTree.Node} Node having the maximum key value that
     *     is less than the specified key value.
     */
    findGreatestLessThan(key) {
        if (this.isEmpty()) {
            return null;
        }
        // Splay on the key to move the node with the given key or the last
        // node on the search path to the top of the tree.
        this.splay(key);
        // Now the result is either the root node or the greatest node in
        // the left subtree.
        if (Number(this.root.key) < key) {
            return this.root;
        }
        else if (this.root.left) {
            return this.findMax(this.root.left);
        }
        else {
            return null;
        }
    }
    /**
     * @return {Array<*>} An array containing all the keys of tree's nodes.
     */
    exportKeys() {
        const result = [];
        if (!this.isEmpty()) {
            this.root.traverse(node => {
                result.push(node.key);
            });
        }
        return result;
    }
    /**
     ** Perform the splay operation for the given key. Moves the node with
     ** the given key to the top of the tree.  If no node has the given
     ** key, the last node on the search path is moved to the top of the
     ** tree. This is the simplified top-down splaying algorithm from:
     ** "Self-adjusting Binary Search Trees" by Sleator and Tarjan
     *
     ** @param {number} key Key to splay the tree on.
     ** @private
     **/
    splay(key) {
        if (this.isEmpty()) {
            return;
        }
        let dummy;
        let left;
        let right;
        dummy = new Node(0, null);
        left = dummy;
        right = dummy;
        let current = this.root;
        while (true) {
            if (key < Number(current.key)) {
                if (!current.left) {
                    break;
                }
                if (key < Number(current.left.key)) {
                    let temp = current.left;
                    current.left = temp.right;
                    temp.right = current;
                    current = temp;
                    if (!current.left) {
                        break;
                    }
                }
                right.left = current;
                right = current;
                current = current.left;
            }
            else if (key > Number(current.key)) {
                if (!current.right) {
                    break;
                }
                if (key > Number(current.right.key)) {
                    let temp = current.right;
                    current.right = temp.left;
                    temp.left = current;
                    current = temp;
                    if (!current.right) {
                        break;
                    }
                }
                left.right = current;
                left = current;
                current = current.right;
            }
            else {
                break;
            }
        }
        // Assemble.
        left.right = current.left;
        right.left = current.right;
        current.left = dummy.right;
        current.right = dummy.left;
        this.root = current;
    }
}
/**
 * Constructs a Splay tree node.
 *
 * @param {number} key Key.
 * @param {*} value Value.
 */
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.right = null;
        this.left = null;
    }
    /**
     * Performs an ordered traversal of the subtree starting at
     * this SplayTree.Node.
     *
     * @param {function(SplayTree.Node)} f Visitor function.
     * @private
     */
    traverse(f) {
        traverseSub(this, f);
    }
}
function traverseSub(current, f) {
    while (current) {
        let left = current.left;
        if (left) {
            left.traverse(f);
        }
        f(current);
        current = current.right;
    }
}
function deBugLog(str) {
    let isLog = false;
    if (isLog) {
        console.log(str);
    }
}
function splayRunIteration() {
    let setupStart = Performance.now();
    let splay = new Splay();
    splay.splaySetup();
    let setupEnd = Performance.now();
    //deBugLog("setupTime: " + String(setupEnd - setupStart) + "ms")
    for (let i = 0; i < SPLAY_120; ++i) {
        for (let i = 0; i < SPLAY_50; ++i) {
            splay.splayRun();
        }
    }
    splay.splayTearDown();
    let splayEnd = Performance.now();
    console.log('splay: ms = ' + String(splayEnd - setupStart));
}
splayRunIteration();
